Machine-implementable page replacement methods have been used to control the movement of pages and to effect the dynamic association between the logical address space and the physical address space of a storage hierarchy. However, performance measures, such as hit/miss ratios, could not be used dynamically in order to "tune" cache performance with respect to cache size and the selection of pageable groups of data from a data base. This inability to dynamically tune performance resulted from the fact that for a given group of pageable data in a data base, the determination of hit/miss ratios as a function of cache size involved a computational complexity proportional to the size of the pageable group of data. Since these pageable groups were typically very large, then the hit/miss ratios could be ascertained only offline at considerable computational expense.
The prior art teaches that a hierarchical storage system having an LRU/MRU page replacement policy requires a substantially smaller number of pages subject to an accessible demand paging regimen than a single level store. The performance of the caches (buffered stages), as has been previously been mentioned, has been characterized by hit/miss ratios. A "hit" means that a READ reference to the cache generated by a requesting CPU executable process locates the data item it desires in the high-speed cache, rather than in a lower speed backing store. A "hit" with respect to a WRITE reference is made when the CPU-executable process through the cache manager finds a counterpart location in a partially full buffer to overwrite. In this regard, a "miss" is registered if the data is unavailable in cache with respect to a READ reference or if an item must be destaged to make room for a WRITE reference.
If data must be destaged or staged up between the small high-speed cache and the larger, but slower, backing store, staging algorithms are required. Popular algorithms, such as least recently used (LRU) or most recently used (MRU), maintain in the cache inventory those items which, more likely than not, will be referenced by a CPU-executable process in the future. A cache not containing a referenced item and otherwise full must remove one of its data elements so that it can be replaced by the requested item. Thus, the system tries to replace the least recently referenced item under the assumption that items which have not been referenced for a long time will not likely be referenced in the future.
The sharing of a high-speed cache among sequential tasks concurrently executing either on a single CPU or among several CPU's is known. In such an environment, a CPU and counterpart hierarchical storage system invoke a global cache management policy permitting equal access to all requesting processes to a scarce resource. This scarce resource is, namely, insufficient cache space. Further, the prior art teaches the use of fixed constraints to regulate or assign cache space. For example, if drums and discs are used to hold pages for all of the system's users, with the system maintaining the most frequently used pages on a drum, some users who rapidly access every page in their page space exactly once and then repeat could take over all the drum space at the expense of other users. For reasons of this type, a cache manager puts a fixed maximum limit on a number of pages any user can occupy. Other systems might assign a different fixed limit for each user. However, once a limit has been assigned, it is the typical experience that after a user fills his cache space he may have a low hit ratio. Also, if during a time interval an executing process references a cache too rapidly with respect to a fixed space allocation, the space limit may be progressively reduced for the next time interval, and vice versa. In this scheme, two or more contending processes, one moving relatively fast and the other relatively slow, might result in the slower user dominating the cache space.
The following references are illustrative of the state of the art. Mattson, et al, "Evaluation Techniques for Storage Hierarchies," IBM Systems Journal No. 2, 1970, pages 78-117, teaches that hit/miss ratios for a given LRU page replacement method in a storage hierarchy can be measured as a function of data set groups and cache size in a single pass. Advantageously, the time required is proportional to the data base size.
Mattson, "Storage Management of Linear Lists by Ordinal Numbers", IBM Technical Disclosure Bulletin, Vol. 19, December 1976, pages 2709-2714, describes a method and means for determining the stack distance of the currently referenced item and then updating of the entire stack in a single memory READ/WRITE cycle for cache-stored LRU lists. Advantageously, the lists could be maintained in real time without slowing the CPU. In this regard, both storage management and system measurement using LRU page replacements could be accomplished at considerable hardware expense, the amount of hardware again being proportional to the data base size. Additionally, this reference merely sets forth the determination of cache size. It does not teach the selection of what prospective data set group is to be placed in the cache. Lawler, in "Fast Approximation Algorithms for Knapsacks Problems," Mathematics of Operations Research, Vol. 4, November 1979, pp. 339-356, describes a method for selecting one cache size (from p+1 cache sizes) from each of q groups of cache sizes, such that the sum of the q cache sizes is less than the system cache size and the sum of the hits obtained from each cache size is maximum. However, Lawler, as does the aforementioned prior art, failed to teach efficient cache allocation in a dynamic paging environment.